#ifndef _TIMER_WHEEL_H_
#define _TIMER_WHEEL_H_

#include "Timer_Queue.h"

// Forward declaration
template <class TYPE>
class Timer_Wheel;


template <class TYPE>
class Timer_Wheel_Iterator
	: public Timer_Queue_Iterator<TYPE>
{
public:
	typedef Timer_Wheel<TYPE> Wheel;
	typedef Timer_Node<TYPE> Node;

	/// Constructor
	Timer_Wheel_Iterator (Wheel &);

	/// Destructor
	~Timer_Wheel_Iterator (void);

	/// Positions the iterator at the earliest node in the Timer Queue
	virtual void first (void);

	/// Positions the iterator at the next node in the Timer Queue
	virtual void next (void);

	/// Returns true when there are no more nodes in the sequence
	virtual int isdone (void) const;

	/// Returns the node at the current position in the sequence
	virtual Timer_Node<TYPE>* item (void);

protected:
	/// Pointer to the <ACE_Timer_List> that we are iterating over.
	Wheel& timer_wheel_;

	/// Current position in the timing wheel
	unsigned int spoke_;

	/// Pointer to the position in the the <pos_>th list
	Timer_Node<TYPE>* current_node_;
private:
	void goto_next( unsigned int start_spoke);
};



template <class TYPE >
class Timer_Wheel : public Timer_Queue<TYPE>
{
public:
	/// Type of iterator
	typedef Timer_Wheel_Iterator<TYPE> Iterator;
	/// Iterator is a friend
	friend class Timer_Wheel_Iterator<TYPE>;
	typedef Timer_Node<TYPE> Node;
	/// Type inherited from
	typedef Timer_Queue<TYPE> Base;
	typedef std::list<Node> FreeList;


	/// Constructor with opportunities to set the wheelsize and resolution
	Timer_Wheel ( unsigned int spoke_count,
		unsigned int resolution,
		size_t prealloc = 0,
		FreeList* freelist = 0);

	/// Destructor
	virtual ~Timer_Wheel (void);

	/// True if queue is empty, else false.
	virtual int is_empty (void) const;

	virtual unsigned long earliest_time (void) const;

	/// Changes the interval of a timer
	virtual int reset_interval (long timer_id,
		unsigned long interval);

	/// Cancel all timer associated with <type>.  If <dont_call> is 0
	/// then the <functor> will be invoked.  Returns number of timers
	/// cancelled.
	virtual int cancel (const TYPE& type,
		int dont_call_handle_close = 1);

	// Cancel a timer, storing the magic cookie in arg (if nonzero).
	// Calls the functor if dont_call_handle_close is 0 and returns 1
	// on success
	virtual int cancel (long timer_id,
		const void** arg = 0,
		int dont_call_handle_close = 1);

	/// Run the <functor> for all timers whose values are <=
	/// <ACE_OS::gettimeofday>.  Also accounts for <timer_skew>.  Returns
	/// the number of timers canceled.
	virtual int expire (void);

	// Run the <functor> for all timers whose values are <= <cur_time>.
	// This does not account for <timer_skew>.  Returns the number of
	// timers canceled.
	int expire (unsigned long);

	/// Returns a pointer to this <Timer_Queue>'s iterator.
	virtual Timer_Queue_Iterator<TYPE>& iter (void);

	/// Removes the earliest node from the queue and returns it
	virtual Timer_Node<TYPE>* remove_first (void);

	/// Reads the earliest node from the queue and returns it.
	virtual Timer_Node<TYPE>* get_first (void);

protected:

	/// Schedules a timer.
	virtual long schedule_i (const TYPE& type,
		const void* arg,
		unsigned long future_time,
		unsigned long interval);

private:
	// The following are documented in the .cpp file.
	Timer_Node<TYPE>* get_first_i (void) const;
	Timer_Node<TYPE>* remove_first_expired (unsigned long now);
	void open_i (size_t prealloc, unsigned int spokes, unsigned int res);
	virtual void reschedule (Timer_Node<TYPE> *);
	Timer_Node<TYPE>* find_spoke_node(unsigned int spoke, long timer_id) const;
	Timer_Node<TYPE>* find_node(long timer_id) const;
	unsigned int calculate_spoke(unsigned long expire) const;
	long generate_timer_id(unsigned int spoke);
	void schedule_i (Timer_Node<TYPE>* n, unsigned int spoke, unsigned long expire);
	void cancel_i (Timer_Node<TYPE>* n);
	void unlink (Timer_Node<TYPE>* n);
	void recalc_earliest(unsigned long last);

private:
	int power2bits (int n, int min_bits, int max_bits);

	/// Timing Wheel.
	Timer_Node<TYPE>** spokes_;
	/// Size of the timing wheel.
	unsigned int spoke_count_;
	/// Number of timer_id bits used for the spoke
	int spoke_bits_;
	/// Maximum number of timers per spoke
	unsigned int max_per_spoke_;
	/// Resolution (in microsoconds) of the timing wheel.
	int res_bits_;
	/// Index of the list with the earliest time
	unsigned int earliest_spoke_;
	/// Iterator used to expire timers.
	Iterator* iterator_;
	/// The total amount of time in one iteration of the wheel. (resolution * spoke_count)
	unsigned long wheel_time_;
	/// The total number of timers currently scheduled.
	unsigned int timer_count_;

};

#include "Timer_Wheel.cpp"

#endif//_TIMER_WHEEL_H_